'''
@Author: shj
@Date: 2020-06-02 19:36:28
@LastEditTime: 2020-06-05 19:39:55
@LastEditors: shj
@Description:  树的子结构
@FilePath: /python3/algorithms/offer_code/17_the_substructure_of_tree.py
'''
''''
题目描述
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:         给定树 B:
    3                 4
   / \               /
  4   5             1
 / \
1   2
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。


思路

若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：

    1. 先序遍历树 A 中的每个节点 nA ；（对应函数 isSubStructure(A, B)）
    2. 判断树 A 中 以 nA​ 为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）

算法流程：

    名词规定：树 A 的根节点记作 节点 A ，树 B 的根节点称为 节点 B 。

recur(A, B) 函数：

    1. 终止条件：
        1. 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true；
        2. 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false；
        3. 当节点 A 和 B 的值不同：说明匹配失败，返回 false；
    2. 返回值：
        判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ；
        判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；

isSubStructure(A, B) 函数：

    1. 特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false；
    2. 返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
        1. 以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
        2. 树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
        3. 树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；
        
        以上 2. 3. 实质上是在对树 A 做 先序遍历 。

复杂度分析：

    时间复杂度 O(MN)： 其中 M,N 分别为树 A 和 树 B 的节点数量；先序遍历树 A 占用 O(M)，每次调用 recur(A, B) 判断占用 O(N) 。
    空间复杂度 O(M)： 当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M≤N 时，遍历树 A 与递归判断的总递归深度为 M；当 M>N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。
''''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''
注释：
def function(params:expression) -> expression:
    pass
    return params
函数中的:expression 和 -> expression叫做函数注释.
对变量和返回类型进行注释,方便更好的理解函数.
这些注释内容是给人看的,你可以注释任何内容.python的解释器不会对注释内容进行校验.
'''
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        # 递归
        def recur(A, B):
            # 递归出口
            if not B:# B树遍历完，B是A的子树
                return True
            # A树先遍历完或出现比较中A、B节点不相等，匹配失败
            if not A or A.val != B.val:
                return False
            # 递归遍历A、B的左右子树
            return recur(A.left, B.left) and recur(A.right, B.right)
        # 如果 A、B树均非空树，且 B是A树跟节点的子树 或 B是A左（右）子树的子树
        return bool(A and B) and ((recur(A, B)) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right , B))